package com.example.lcode.binary;

import java.util.Arrays;

public class Question436 {

    public int[] findRightInterval(int[][] intervals) {
        int[][] copyIntervals = new int[intervals.length][3];
        for (int i = 0; i < intervals.length; i++) {
            copyIntervals[i][0] = intervals[i][0];
            copyIntervals[i][1] = intervals[i][1];
            copyIntervals[i][2] = i;
        }
        int  _index112 = 1;
        Arrays.sort(copyIntervals, (o1, o2) -> {
            return o1[0] - o2[0];
        });
        int []res = new int[copyIntervals.length];
        for (int i = 0; i < copyIntervals.length; i++) {
            res[copyIntervals[i][2]] = findIndex(copyIntervals, i, copyIntervals.length - 1, copyIntervals[i][1]);
        }
        return res;
    }

    private int findIndex(int[][] intervals, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (intervals[mid][0] >= target && (mid == 0 || intervals[mid - 1][0] < target)) {
            return intervals[mid][2];
        } else if (mid != 0 && intervals[mid - 1][0] >= target){
            return findIndex(intervals, left, mid - 1, target);
        } else {
            return findIndex(intervals, mid + 1, right, target);
        }
    }

    public static void main(String[] args) {
        Question436 question436 = new Question436();
        int [][]arrs = {{1,1},{3,4}};
        int[] rightInterval = question436.findRightInterval(arrs);
        for (int i = 0; i < rightInterval.length ; i++) {
            System.out.print(rightInterval[i] + " ");
        }
    }


}
